GENERALIZED INDETERMINISTIC FINITE AUTOMATA 

Baumgertner Svetlana Viktorovna, Candidate of physical and mathematical sciences, senior lecturer, sub-department of applied mathematics and informatics, Togliatti State University (Togliatti, 14 Belorusskaya str.),     S-Baumgertner@yandex.ru
Mel'nikov Boris Feliksovich, Doctor of physical and mathematical sciences, professor, sub-department of applied mathematics and informatics, Togliatti State University (Togliatti, 14 Belorusskaya str.), B.Melnikov@tltsu.ru 

519.178 

The article considers the formalism used for representing a special class of extensions of finite automata, so-called generalized indeterministic finite automata. The described algorithms of equivalent transformations of such automata and also their analogue of Kleene theorem result in not only the equivalence between such and usual finite automata (such equivalence is obvious a priori), but also in the possibility of defining the complement operation (and, generally, the generalized regular expressions) by usual “automata” methods. The work also describes the construction method of the specific generalized automaton, which determines the given generalized regular expression. The given method results from the Kleene theorem analogue proving. Extended opportunities for regular languages description introduced in the article may be of use in several applications, e.g. in contextual search.

indeterministic finite automaton, generalized regular expressions, algorithms of equivalent transformation, analogue of Kleene theorem. 

1. Baumgertner S., Mel'nikov B. Vestnik Voronezhskogo gosudarstvennogo universiteta. Seriya: Cistemnyy analiz i informatsionnye tekhnologii [Voronezh state university bulletin. Series: System analysis and information technologies]. 2010, no. 1, pp. 5–7.
2. Baumgertner S., Mel'nikov B. Evristicheskie algoritmy i raspredelennye vychisleniya v prikladnykh zadachakh : kol. monogr. [Heuristic algorithms and distributed computing in applied problems: joint monograph]. Tolyatti: Izd-vo TGU, 2012, pp. 16–23.
3. Baumgertner S. Vektor nauki Tol'yattinskogo gosudarstvennogo universiteta [Science vector of Togliatti state university]. 2012, no. 4 (22), pp. 23–25.
4. Salomaa A. Zhemchuzhiny teorii formal'nykh yazykov [Pearls of the formal languages theory]. Moscow: Mir, 1986, 159 p.
5. Melnikov B. Fundamenta Informaticae. 2010, vol. 104, no. 3, pp. 255–265.
6. Melnikov B., Vakhitova A. J. of Applied Math. and Comp. (The Korean J. of Comp. Appl. Math.). 1998, vol. 5, no 3, pp. 495–506.
7. Melnikov B. Fundamenta Informaticae. 2010, vol. 104, no. 3, pp. 267–283.